Masala #0223

Matematikada ko’pchiligingiz rekurrent formula haqida eshitgan bo’lsangiz kerak. Rekurrent formulada berilan ketma-ketlikning elementi uning boshqa elementlariga bog’liq bo’ladi. Hozirgi masalada ham rekurrent formula bilan ketma-ketlik berilgan.

$A_{n+3}-6*A_{n+2}+11*A_{n+1}-6*A_{n}=0$

$A_1=3, A_2=15, A_3=41;$

Sizning vazifangiz ketma-ketlikning $A_n$ hadini $10^9+7$ ga bo’lgndagi qoldiqni chiqarishingiz kerak.

Bitta $n$ butun son $1 \le n \le 10^{15}$

$A_n$ ketma-ketlikni hadi